home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / basic / _basic_alg.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  1.5 KB  |  98 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _basic_alg.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/basic_alg.h>
  17.  
  18. #define SWAP(a,b) { help = *a; *a = *b; *b = help; }
  19.  
  20.  
  21. int SELECT(int* l, int* r, int pos)
  22. { 
  23.   // compute element at position "pos" in sequence *l,...,*r
  24.   // expected running time: O(r-l)
  25.  
  26.   register int* i;
  27.   register int* k;
  28.   register int s;
  29.   register int help;
  30.  
  31.   while (l < r) 
  32.   { i = l+(r-l)/2;
  33.     if (*i > *r) SWAP(i,r);
  34.     SWAP(l,i);
  35.  
  36.     i = l;
  37.     k = r;
  38.     s = *l;
  39.  
  40.     for(;;)
  41.     { while (*(++i) < s);
  42.       while (*(--k) > s);
  43.       if (i<k) SWAP(i,k) else break;
  44.      }
  45.   
  46.     SWAP(l,k);
  47.   
  48.     int j =  k-l+1;
  49.     if (pos <= j) 
  50.        r = k;
  51.     else 
  52.        { l = k+1;
  53.          pos -= j;
  54.         }
  55.   }
  56.  
  57.   return *l;
  58. }
  59.  
  60.  
  61.  
  62. double SELECT(double* l, double* r, int pos)
  63. { 
  64.   register double* i;
  65.   register double* k;
  66.   register double s;
  67.   register double help;
  68.  
  69.   while (l < r) 
  70.   { i = l+(r-l)/2;
  71.     if (*i > *r) SWAP(i,r);
  72.     SWAP(l,i);
  73.  
  74.     i = l;
  75.     k = r;
  76.     s = *l;
  77.  
  78.     for(;;)
  79.     { while (*(++i) < s);
  80.       while (*(--k) > s);
  81.       if (i<k) SWAP(i,k) else break;
  82.      }
  83.   
  84.     SWAP(l,k);
  85.   
  86.     int j =  k-l+1;
  87.     if (pos <= j) 
  88.        r = k;
  89.     else 
  90.        { l = k+1;
  91.          pos -= j;
  92.         }
  93.   }
  94.  
  95.   return *l;
  96. }
  97.  
  98.